package com.xzz.tree;

/**
 * @author: hhz
 * @create: 2022-01-20 16:45
 * 112. 路径总和
 **/
public class HasPathSum {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(11);
        TreeNode node5 = new TreeNode(13);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(2);
        TreeNode node9 = new TreeNode(1);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.left = node6;
        node4.left = node7;
        node4.right = node8;
        node5.right = node9;

        System.out.println(hasPathSum(node1,22));
    }
    static boolean res = false;
    static int curSum = 0;
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        res = false;
        curSum = 0;
        traverse(root,targetSum);
        return res;
    }

    public static void traverse(TreeNode root,int targetSum) {
        if(root==null){
            return ;
        }
        curSum+=root.val;
        if(root.left ==null && root.right==null){
            if(curSum ==targetSum){
                res = true;
            }
        }
        traverse(root.left,targetSum);
        traverse(root.right,targetSum);
        curSum-=root.val;
    }
}
